package com.wuyou.mid;

import sun.nio.cs.ext.MacHebrew;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串
 * 。
 *
 * @Date 2024/12/18 15:48
 * @Author 无忧
 */
public class LongestPalindrome{

    public static void main(String[] args) {
        LongestPalindrome longestPalindrome = new LongestPalindrome();
        String s="cbbd";
        System.out.println(longestPalindrome.longestPalindrome(s));
    }

    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        char[] chars=s.toCharArray();
        int length=chars.length;
        int[][] resArr=new int[2][2];
        for(int i=0;i<length;i++){
            resArr=palindrome(chars,i,resArr);
        }
        return s.substring(resArr[1][0], resArr[1][1]);
    }

    /**
     * 回文检测：左右相等。长度为奇数，chars[i]左右相等；长度为偶数，chars[i]=chars[i+1]
     * @param chars
     * @param i
     * @return
     */
    private int[][] palindrome(char[] chars,int i,int[][] resArr){
        int max=resArr[0][0];
        int begin=i,end=i;
        while(begin>0&&end<chars.length-1&&chars[begin-1]==chars[end+1]){
            begin--;
            end++;
        }
        int begin1=i,end1=i;
        if(i<chars.length-1&&chars[begin1]==chars[end1+1]){
            end1++;
            while (begin1>0&&end1<chars.length-1&&chars[begin1-1]==chars[end1+1]){
                begin1--;
                end1++;
            }
        }
        if (end+1-begin>max) {
            resArr[1][0] = begin;
            resArr[1][1] = end+1;
            max=end+1-begin;
        }
        if (end1+1-begin1>max) {
            resArr[1][0] = begin1;
            resArr[1][1] = end1+1;
            max=end1+1-begin1;
        }
        resArr[0][0]=max;
        return resArr;
    }
}
